// 题目要求：
// 给定一个整数 n，求和为 n 的完全平方数的最少个数

// 解题思路：
// 完全背包问题：
// 假设 t = sqrt(n)，这道题目可以转化为 从 [1, t] 的平方数中挑数字，要求和为 n 的最少的数字个数，数字可以重复挑
// 因此题目就转化成了一个完全背包问题
// dp[i][j] 表示从 [0, i] 中挑和为 j 的完全平方数的个数
// 如果不选 i，dp[i][j] = dp[i - 1][j]
// 如果 j - i * i >= 0，考虑可以选 i，dp[i][j] = dp[i][j - i * i] + 1
// 从上述两种情况中选最小值

// 初始化：
// j >= 1: dp[0][j] = 0x3f3f3f3f 表示从 0 中挑不出完全平方数，使得和为 j
// 因为题目要求挑最小值，因此把这个数字初始化为整数最大值的一半，取最小值的时候就不会选取到

import java.util.*;

public class PerfectSquare {
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);

        int n = in.nextInt();
        int t = (int)Math.sqrt(n);
        int[][] dp = new int[t + 1][n + 1];

        for(int j = 1; j <= n; j++){
            dp[0][j] = 0x3f3f3f3f;
        }

        for(int i = 1; i <= t; i++){
            for(int j = 0; j <= n; j++){
                dp[i][j] = dp[i - 1][j];
                if(j - i * i >= 0){
                    dp[i][j] = Math.min(dp[i][j], dp[i][j - i * i] + 1);
                }
            }
        }

        System.out.println(dp[t][n]);
    }
}
